package utils;

import java.util.List;
import java.util.PriorityQueue;

public class crud_lianbiao {
    public class ListNode{     //创建一个ListNode的表
        int val;
        ListNode next;
        ListNode(int x){
            val=x;
        }
    }
    public ListNode initLists(int a[]){
        ListNode head=new ListNode(0);   //虚拟头结点head，返回时，返回head.next
        ListNode cur=head;     //中间节点
        for(int i:a){
            ListNode listNode=new ListNode(i);
            cur.next=listNode;
            cur=cur.next;

        }
        return head.next;
    }
    //给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
    public  ListNode quchong(ListNode root){
        ListNode head=new ListNode(-1);
        head.next=root;
        ListNode pre=head;
        ListNode next=root;
        while(next!=null&&next.next!=null) {
           if(next.val==next.next.val){
               ListNode temp=next.next;
               while (temp!=null&&temp.val==next.val){
                   temp=temp.next;
               }
               pre.next=temp;
               next=temp;
           }
           else {
               pre=pre.next;
               next=next.next;
           }
        }
        return head.next;
    }
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        ListNode head;    //创建一个头结点
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<=l2.val){   //初始化head
            head=l1;
            l1=l1.next;
        }else {
            head=l2;
            l2=l2.next;
        }
        ListNode curr=head;
        while (l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                curr.next=l1;
                curr=curr.next;  //将指针跳转到下一个位置,不能改变头指针head，因为那是记录头指针的
                l1=l1.next;
            }else {
                curr.next=l2;
                curr=curr.next;
                l2=l2.next;
            }
        }
        if(l1==null&&l2!=null)
            curr.next=l2;
        if(l2==null&&l1!=null)
            curr.next=l1;
        return head;
    }
    public  void visit(ListNode listNode){
        System.out.println("遍历结果为");
        while (listNode!=null){
            System.out.print(listNode.val);
            listNode=listNode.next;
        }
    }
    public ListNode deleteListNode(ListNode listNode,int a){
        ListNode head=listNode;
        ListNode next=listNode.next;
        if(listNode.val==a)
            head=listNode.next;
        else {
            while (next != null) {
                if (next.val != a) {
                    listNode = next;
                } else {
                    listNode.next = next.next;
                }
                next = next.next;
            }
        }
        return head;
    }
    public ListNode addList(ListNode listNode,int a){
        ListNode head=listNode;
        ListNode listNode1=new ListNode(a);
       // listNode1.next=null;
        for(int i=0;i<1;i++){
            listNode=listNode.next;
        }
        listNode1.next=listNode.next;
        listNode.next=listNode1;
        return head;
    }
    //小顶堆方式实现k链表连接
    public  ListNode mergeKList(List<ListNode> listNodes){
        if(listNodes==null) return null;
        ListNode head=new ListNode(0);
        ListNode cur=head;
        //将所有链表的头结点添加到小顶堆中(优先级队列中)
        PriorityQueue<ListNode> priorityQueue=new PriorityQueue<>((ListNode n1,ListNode n2)->{ return n1.val-n2.val;});   //创建一个比较器
        for (ListNode l:listNodes){
     priorityQueue.offer(l);  //入堆
        }
        //不断删除元素，并把堆顶元素的next添加到堆中
        while (!priorityQueue.isEmpty()){
           ListNode npde= priorityQueue.poll();  //删除堆顶元素
            cur=cur.next=npde;
            if(npde.next!=null){
                priorityQueue.offer(npde.next);
            }
        }
     return head.next;
    }
    //3、使用分治算法实现
public ListNode fenZhiMerge(List<ListNode> listNodes){
    if(listNodes==null||listNodes.size()==0) return null;
    int step=1;
    while (step<listNodes.size()) {
        for (int i = 0; i + step < listNodes.size(); i += 2 * step) {
            //先将两条进行合并
          listNodes.set(i ,mergeTwoLists(listNodes.get(i), listNodes.get(i + step)));
        }
        step *= 2;    //每次长度就除二，步数增长2倍
    }
    return listNodes.get(0);
    }
}
